부산대학교자료구조
Scientific Inference Lab

Data Abstraction

Choosing an ADT

자료구조 이름보다 필요한 연산을 먼저 정한다. 요구사항이 위치, 같은 값, 순서, 삭제 순서 가운데 무엇을 묻는지 먼저 가른다.

위치리스트(list)는 인덱스로 조회하고 바꾼다.
값과 순서USet은 같은 값, SSet은 기준 이상인 가장 작은 값을 찾는다.
삭제 순서스택은 최근 원소, 큐는 먼저 온 원소, 우선순위 큐는 우선순위가 가장 높은 원소를 삭제한다.

필요한 연산이 ADT 선택을 가른다

요구사항을 고르면 필요한 연산과 그 연산을 직접 제공하는 ADT의 행이 강조된다.

필요한 연산리스트USetSSet스택큐우선순위 큐
위치 i 조회·삽입get(i), add(i,x)해당 없음해당 없음해당 없음해당 없음해당 없음
같은 값 또는 없음해당 없음find(x)다른 의미의 find해당 없음해당 없음해당 없음
x 이상인 가장 작은 값 또는 없음해당 없음다른 의미의 findfind(x)해당 없음해당 없음해당 없음
마지막 원소 삭제·반환위치 연산 필요해당 없음해당 없음pop()삭제 순서가 다름삭제 기준이 다름
첫 원소 삭제·반환위치 연산 필요해당 없음해당 없음삭제 순서가 다름dequeue()삭제 기준이 다름
우선순위가 가장 높은 원소 삭제·반환해당 없음해당 없음해당 없음삭제 기준이 다름삭제 기준이 다름remove()
초록 막대가 있는 행은 고른 요구사항이고, 굵은 글씨 칸은 그 요구를 직접 제공하는 연산이다.

같은 저장 값도 질문에 따라 호출이 달라진다

각 카드는 해당 ADT가 돌려주는 결과를 보여 준다. 같은 값을 저장해도 자료형에 따라 답할 수 있는 질문이 다르다.

리스트 [3, 7, 10]get(1) → 7위치 1의 값
USet {3, 7, 10}find(6) → None6과 같은 값이 없음
SSet {3, 7, 10}find(6) → 76 이상인 가장 작은 값
스택 [3, 7, 10]pop() → 10가장 최근 원소
큐 [3, 7, 10]dequeue() → 3가장 먼저 들어온 원소
우선순위 큐 {3, 7, 10}remove() → 3숫자가 작을수록 우선할 때 가장 높은 우선순위

저장된 값보다 필요한 반환값, 위치 조건, 순서 조건이 ADT 선택을 결정한다. Python의 list도 pop()을 부르면 스택처럼, deque의 popleft()를 부르면 큐처럼 쓰인다. 자료형 이름만으로 ADT를 단정할 수 없다.